package com.leetcode.alibaba;

import lombok.Data;

/**
 * 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
 * 数据范围： 0 \le n \le 10000≤n≤1000，-1000 \le 节点值 \le 1000−1000≤节点值≤1000
 * 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 * <p>
 * 如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}
 */
public class 链表合并 {

	public static void main(String[] args) {
		ListNode list1 = new ListNode(1);
		ListNode list3 = new ListNode(3);
		ListNode list5 = new ListNode(5);
		ListNode list2 = new ListNode(2);
		ListNode list4 = new ListNode(4);
		ListNode list6 = new ListNode(6);

		list1.next = list3;
		list3.next = list5;
		list2.next = list4;
		list4.next = list6;

		System.out.println(list1);

		ListNode mergeNode = merge2(list1, list2);
		System.out.println(mergeNode);
	}

	/**
	 * 方法一：遍历比较，用双链表
	 *
	 * @param list1
	 * @param list2
	 * @return
	 */
	public static ListNode merge(ListNode list1, ListNode list2) {
		if (list1 == null) {
			return list2;
		}
		if (list2 == null) {
			return list1;
		}
		ListNode newHead = new ListNode(-1);
		ListNode newHeadTemp = newHead;
		ListNode temp1 = list1;
		ListNode temp2 = list2;
		while (temp1 != null && temp2 != null) {
			if (temp1.val < temp2.val) {
				newHeadTemp.next = temp1;
				temp1 = temp1.next;
			} else {
				newHeadTemp.next = temp2;
				temp2 = temp2.next;
			}
			newHeadTemp = newHeadTemp.next;
		}
		if (temp1 != null) {
			newHeadTemp.next = temp1;
		}
		if (temp2 != null) {
			newHeadTemp.next = temp2;
		}
		return newHead.next;
	}

	/**
	 * 方法二：递归
	 *
	 * @param list1
	 * @param list2
	 * @return
	 */
	public static ListNode merge2(ListNode list1, ListNode list2) {
		if (list1 == null) {
			return list2;
		}
		if (list2 == null) {
			return list1;
		}
		if (list1.val < list2.val) {
			list1.next = merge(list1.next, list2);
			return list1;
		} else {
			list2.next = merge(list1, list2.next);
			return list2;
		}
	}

}

@Data
class ListNode {
	int val;
	ListNode next = null;

	ListNode(int val) {
		this.val = val;
	}
}
